// merge sort 归并排序示例代码。
// 归并排序采用分治（ Divide and Conquer ）的思想，把数组切分成更小的部分，然后再从小到大合并。
// 归并排序是不稳定排序方法（无法保证相同的值的前后顺序），
// 平均时间复杂度 O(N*logN) ，最坏时间复杂度 O(N*logN) 。
#include <stdio.h>

// 按照从小到大的顺序合并结果到数组 arr ，
// [first, mid] 和 [mid + 1, last] 两段数组已经被从小到大排序。
static void
MergeArray(int *arr, int first, int mid, int last, int *temp) {
	int i = first, j = mid + 1, k = 0;
	while (i <= mid && j <= last) {
		if (arr[i] <= arr[j])
			temp[k++] = arr[i++];
		else
			temp[k++] = arr[j++];
	}

	while (i <= mid)
		temp[k++] = arr[i++];
	while (j <= last)
		temp[k++] = arr[j++];

	for (i = 0; i < k; i++) // 合并结果
		arr[first + i] = temp[i];
}

// 从小到大排序数组中 first ~ last 索引范围内的元素。
static void
_MergeSort(int *arr, int first, int last, int *temp) {
	if (first < last) {
		int mid = (first + last) / 2;
		// 切分成小数组排序
		_MergeSort(arr, first, mid, temp);
		_MergeSort(arr, mid + 1, last, temp);
		// 把有序的小数组合并
		MergeArray(arr, first, mid, last, temp);
	}
}

void
MergeSort(int *arr, int len, int *cache) {
	_MergeSort(arr, 0, len - 1, cache);
}

int
main() {
	int arr[] = {1000, 100, -100, 0, 300, 4000, -50, -20, -1000, 1000};
	int len = sizeof(arr)/sizeof(arr[0]);
	int cache[len];

	for (int i = 0; i < len; i++)
		printf("%d ", arr[i]);
	MergeSort(arr, len, cache);
	printf("\nafter sorting:\n");
	for (int i = 0; i < len; i++)
		printf("%d ", arr[i]);
	printf("\n");
	return 0;
}
